package org.example.code.test2024.nine_mouth;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class tst0924 {
    public boolean reportSpam(String[] message, String[] bannedWords) {
        Map<String, Integer> map = new HashMap<>();
        for (String msg : bannedWords) {
            map.put(msg, 0);
        }
        int sum = 0;
        for (String msg : message) {
            if (map.containsKey(msg)) {
                sum++;
            }

            if (sum == 2) {
                return true;
            }
        }
        return false;
    }

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        // 二分查找的左边界是0，右边界是所有工人以最快的速度降低山的高度总时间
        long left = 0, right = (long) workerTimes[0] * mountainHeight * (mountainHeight + 1) / 2;

        while (left < right) {
            long mid = left + (right - left) / 2;
            if (canReduceToZero(mountainHeight, workerTimes, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // 判断是否可以在给定的时间内将山的高度降低到 0
    private boolean canReduceToZero(int mountainHeight, int[] workerTimes, long timeLimit) {
        long totalHeightReduced = 0;

        for (int time : workerTimes) {
            // 二分查找可以在 timeLimit 内降低的最大高度
            long left = 0, right = mountainHeight;
            while (left < right) {
                long mid = left + (right - left + 1) / 2;
                if (time * mid * (mid + 1) / 2 <= timeLimit) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }

            totalHeightReduced += left;
            if (totalHeightReduced >= mountainHeight) {
                return true;
            }
        }
        return totalHeightReduced >= mountainHeight;
    }

    public long validSubstringCount(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        Map<Character, Integer> countWord2 = new HashMap<>();
        for (char c : word2.toCharArray()) {
            countWord2.put(c, countWord2.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> countWindow = new HashMap<>();
        int left = 0;
        long result = 0;
        int matched = 0;  // 匹配的字符数量

        for (int right = 0; right < n; right++) {
            char rightChar = word1.charAt(right);
            countWindow.put(rightChar, countWindow.getOrDefault(rightChar, 0) + 1);

            // 如果该字符在 word2 中存在，且频次匹配
            if (countWord2.containsKey(rightChar) &&
                    countWindow.get(rightChar).intValue() == countWord2.get(rightChar).intValue()
            ) {
                matched++;
            }

            // 当窗口中的字符频次与 word2 完全匹配
            while (matched == countWord2.size()) {
                result += (n - right);  // 从 right 到字符串末尾的所有子串都是合法的

                // 缩小左端，移除左边的字符
                char leftChar = word1.charAt(left);
                countWindow.put(leftChar, countWindow.get(leftChar) - 1);
                if (countWindow.get(leftChar).intValue() < countWord2.getOrDefault(leftChar, 0)) {
                    matched--;  // 如果频次不再匹配，匹配字符数减少
                }
                left++;  // 左端收缩
            }
        }

        return result;
    }
}
